|
A carry-save adder〔Earle, J. G. et al "Latched Carry Save Adder Circuit for Multipliers" filed July 12, 1965〕〔 〕 is a type of digital adder, used in computer microarchitecture to compute the sum of three or more ''n''-bit numbers in binary. It differs from other digital adders in that it outputs two numbers of the same dimensions as the inputs, one which is a sequence of partial sum bits and another which is a sequence of carry bits. ==Motivation== Consider the sum: 12345678.Using basic arithmetic, we calculate right to left, "8+2=0, carry 1", "7+2+1=0, carry 1", "6+3+1=0, carry 1", and so on to the end of the sum. Although we know the last digit of the result at once, we cannot know the first digit until we have gone through every digit in the calculation, passing the carry from each digit to the one on its left. Thus adding two ''n''-digit numbers has to take a time proportional to ''n'', even if the machinery we are using would otherwise be capable of performing many calculations simultaneously. In electronic terms, using bits (binary digits), this means that even if we have ''n'' one-bit adders at our disposal, we still have to allow a time proportional to ''n'' to allow a possible carry to propagate from one end of the number to the other. Until we have done this, # We do not know the result of the addition. # We do not know whether the result of the addition is larger or smaller than a given number (for instance, we do not know whether it is positive or negative). A carry look-ahead adder can reduce the delay. In principle the delay can be reduced so that it is proportional to log''n'', but for large numbers this is no longer the case, because even when carry look-ahead is implemented, the distances that signals have to travel on the chip increase in proportion to ''n'', and propagation delays increase at the same rate. Once we get to the 512-bit to 2048-bit number sizes that are required in public-key cryptography, carry look-ahead is not of much help. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Carry-save adder」の詳細全文を読む スポンサード リンク
|